package main.java.indi.zyj.coderecord;

import java.util.Arrays;

public class FindTargetSumWays {

    /**
     * @Description 总和是sum，设置的负数和为x，正数和 = sum - x，target = （sum - x）- x， x = (sum - target) / 2;
     *              填满j（包括j）这么大容积的包，有dp[j]种方法
     * @param nums
     * @param target
     * @return int
     * @author zyj
     * @date 2024/04/12 12:32
     */
    public int findTargetSumWays(int[] nums, int target) {

        int len = nums.length;
        int sum = 0;

        for (int i = 0; i < len; i++) {
            sum += nums[i];
        }
        if ((sum - target) < 0 || (sum - target) % 2 != 0) {
            return 0;
        }
        int x = (sum - target) / 2;

        // 填满x容量有dp[j]种方法
        int[] dp = new int[x + 1];

        // 填满0容量有1种方法就是不装东西
        dp[0] = 1;

        for (int i = 0; i < len; i++) {
            for (int j = x; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }

        return dp[x];

    }

}
